By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 37, Issue 1, pp. 1-357

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

On the Computational Complexity of the Forcing Chromatic Number

Frank Harary, Wolfgang Slany, and Oleg Verbitsky

pp. 1-19

BibTeX  Abstract Full Text:  PDF

Lower Bounds for Quantum Communication Complexity

Hartmut Klauck

pp. 20-46

BibTeX  Abstract Full Text:  PDF

Adiabatic Quantum State Generation

Dorit Aharonov and Amnon Ta-Shma

pp. 47-82

BibTeX  Abstract Full Text:  PDF

A Probabilistic Study on Combinatorial Expanders and Hashing

Phillip G. Bradford and Michael N. Katehakis

pp. 83-111

BibTeX  Abstract Full Text:  PDF

Hardness of the Undirected Congestion Minimization Problem

Matthew Andrews and Lisa Zhang

pp. 112-131

BibTeX  Abstract Full Text:  PDF

Constraint Satisfaction, Logic and Forbidden Patterns

Florent Madelaine and Iain A. Stewart

pp. 132-163

BibTeX  Abstract Full Text:  PDF
SPECIAL SECTION

Special Section on Foundations of Computer Science

Dimitris Achlioptas and Vladlen Koltun

p. 165

BibTeX  Abstract FREE Full Text:  PDF

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev

pp. 166-194

BibTeX  Abstract Full Text:  PDF

On the List and Bounded Distance Decodability of Reed–Solomon Codes

Qi Cheng and Daqing Wan

pp. 195-209

BibTeX  Abstract Full Text:  PDF

Quantum Walk Algorithm for Element Distinctness

Andris Ambainis

pp. 210-239

BibTeX  Abstract Full Text:  PDF

Dynamic Optimality—Almost

Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Patrascu

pp. 240-251

BibTeX  Abstract Full Text:  PDF

Algebras with Polynomial Identities and Computing the Determinant

Steve Chien and Alistair Sinclair

pp. 252-266

BibTeX  Abstract Full Text:  PDF

Worst-Case to Average-Case Reductions Based on Gaussian Measures

Daniele Micciancio and Oded Regev

pp. 267-302

BibTeX  Abstract Full Text:  PDF

A Polynomial Time Algorithm for Computing an Arrow–Debreu Market Equilibrium for Linear Utilities

Kamal Jain

pp. 303-318

BibTeX  Abstract Full Text:  PDF

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell

pp. 319-357

BibTeX  Abstract Full Text:  PDF